// https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

// 算法思路总结：
// 1. 动态规划求解最长公共子数组（连续）
// 2. dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度
// 3. 元素相等时状态转移：dp[i][j] = dp[i-1][j-1] + 1
// 4. 元素不等时重置为0（子数组要求连续）
// 5. 实时更新最大值ret
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        int ret = 0;
        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (nums1[i - 1] != nums2[j - 1])
                {
                    dp[i][j] = 0;
                }
                else
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums11 = {1,2,3,2,1}, nums12 = {3,2,1,4,7};
    vector<int> nums21 = {0,0,0,0,0}, nums22 = {0,0,0,0,0};

    Solution sol;

    cout << sol.findLength(nums11, nums12) << endl;
    cout << sol.findLength(nums21, nums22) << endl;

    return 0;
}